package com.jiang.daily.Q3607;
import java.util.*;

/**
 * @author Jiang
 * @version 1.0
 * @date 2025/11/06 15:43
 */
class Solution {
    public int[] processQueries(int c, int[][] connections, int[][] queries) {
        int[] parent = new int[c + 1];
        for (int i = 0; i <= c; i++) {
            parent[i] = i;
        }
        for (int[] connection : connections) {
            union(parent, connection[0], connection[1]);
        }

        Deque<Integer>[] queues = new Deque[c + 1];
        for (int i = 1; i <= c; i++) {
            int p = find(parent, i);
            if (queues[p] == null) {
                queues[p] = new ArrayDeque<>();
            }
            queues[p].add(i);
        }

        boolean[] online = new boolean[c + 1];
        Arrays.fill(online, true);

        List<Integer> res = new ArrayList<>();
        for (int[] query : queries) {
            if (query[0] == 1) {
                if (online[query[1]]) {
                    res.add(query[1]);
                } else {
                    int p = find(parent, query[1]);
                    while (!queues[p].isEmpty() && !online[queues[p].peek()]) {
                        queues[p].poll();
                    }
                    if (queues[p].isEmpty()) {
                        res.add(-1);
                    } else {
                        res.add(queues[p].peek());
                    }
                }
            } else {
                online[query[1]] = false;
            }
        }
        return res.stream().mapToInt(Integer::intValue).toArray();
    }
    private int find(int[] parent, int x) {
        if (parent[x] == x) {
            return x;
        }
        parent[x] = find(parent, parent[x]);
        return parent[x];
    }
    private void union(int[] parent, int x, int y) {
        int px = find(parent, x);
        int py = find(parent, y);
        if (px == py) {
            return;
        }
        if (px <= py) {
            parent[py] = px;
        } else {
            parent[px] = py;
        }
    }
}
